package tu;

import java.util.LinkedList;
import java.util.List;

//深度优先遍历
public class Dfs {
    public static void main(String[] args) {
        //进行图的数据添加
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        //List.of介绍，添加数据，后续不能进行新的数据添加，这里实际上一般使用的是Arrays.asList,这里因为数据无需添加，所以用这个就可以实现
        v1.edges = List.of(new Edge(v3), new Edge(v2), new Edge(v6));
        v2.edges = List.of(new Edge(v4));
        v3.edges = List.of(new Edge(v4), new Edge(v6));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5));
        //dfs1(v1);两个实现单独操作
        System.out.println("=============");
        dfs2(v1);
    }

    //使用递归实现dfs1
    public static void dfs1(Vertex v) {
        //修改数据的标记
        v.visited = true;
        //打印相关的值，这里方便查看
        System.out.println(v.name);
        //接下来对该顶点的关联边的顶点进行操作
        for (Edge edge : v.edges) {
            //看关联边的另一个顶点是否已经被访问
            if (!edge.linked.visited) {
                dfs1(edge.linked);
            }
        }
    }

    //不使用递归实现dfs
    public static void dfs2(Vertex vertex) {
        //创建出来一个栈
        LinkedList<Vertex> stack = new LinkedList<>();
        //添加数据
        stack.push(vertex);
        //当栈不为空时即可了，这点无需像树一样
        while (!stack.isEmpty()) {
            //修改是否已经访问过的值
            Vertex pop = stack.pop();
            pop.visited = true;
            System.out.println(pop.name);
            //接下来对该入栈的边的另一个节点进行入栈操作
            for (Edge edge : pop.edges) {
                if (!edge.linked.visited) {
                    stack.push(edge.linked);
                }
            }
        }
    }
}
